package vip.meeet.algorithm.arr;


public class Num4 {

    public static void main(String[] args) {
//        int[] a = {1,3};
//        int[] b = {2};
//        int[] a = {1,2};
//        int[] b = {3,4};
        int[] b = {1,2};
        int[] a = {1,2,3,4,5,6,7,8};
        System.out.println(findMedianSortedArrays(a,b));

    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int lenA = nums1.length;
        int lenB = nums2.length;
        if(lenA > lenB){
            return find(nums1,nums2);
        }else {
            return find(nums2,nums1);
        }
    }

    public static double find(int[] big, int[] small){
        int lenA = big.length;
        int lenB = small.length;
        int totalLen = lenA + lenB;
        int medIndex;
        boolean isOdd;
        if(totalLen % 2 == 0){
            isOdd = true;
            medIndex = totalLen / 2 - 1;
        }else {
            isOdd = false;
            medIndex = totalLen / 2;
        }
        int smallIndex = 0;
        int bigIndex = 0;
        int index = 0;
        while (smallIndex < lenB && bigIndex < lenA && index < medIndex){
            if(small[smallIndex] <= big[bigIndex]){
                smallIndex++;
            }else {
                bigIndex++;
            }
            index++;
        }

        if(smallIndex == lenB){
            int curIndex = medIndex - smallIndex;
            if(!isOdd){
                return big[curIndex];
            }else {
                return (double) (big[curIndex] + big[curIndex + 1]) / 2;
            }
        }
        if(bigIndex == lenA){
            int curIndex = medIndex - bigIndex;
            if(!isOdd){
                return small[curIndex];
            }else {
                return (double) (small[curIndex] + small[curIndex + 1]) / 2;
            }
        }
        if(index == medIndex){
            if(bigIndex < lenA && smallIndex < lenB){
                if(!isOdd){
                    if(small[smallIndex] <= big[bigIndex]){
                        return small[smallIndex];
                    }else {
                        return big[bigIndex];
                    }
                }else {
                    double first,seconde;
                    if(small[smallIndex] <= big[bigIndex]){
                        first = small[smallIndex++];
                    }else {
                        first = big[bigIndex++];
                    }
                    medIndex++;
                    if(smallIndex < lenB && bigIndex < lenA){
                        if(small[smallIndex] <= big[bigIndex]){
                            seconde = small[smallIndex];
                        }else {
                            seconde = big[bigIndex];
                        }
                    }else if(smallIndex == lenB){
                        seconde = big[bigIndex];
                    }else {
                        seconde = small[smallIndex];
                    }
                    return (first + seconde) / 2;
                }
            }else if(smallIndex == lenB){
                if(!isOdd){
                    return big[bigIndex];
                }else {
                    return (double)(big[bigIndex] + big[bigIndex+1]) / 2;
                }
            }else {
                if(!isOdd){
                    return small[smallIndex];
                }else {
                    return (double)(small[smallIndex] + big[smallIndex+1]) / 2;
                }
            }
        }
        return 0;
    }


}
